package com.example.bledemo.tool;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Created by Peter_Z.
 * <p>
 * Date: 2024/10/14 0014
 */
public class PriorityQueue<T extends Comparable<T>> {
    private List<T> items;

    // Getter for the count of items in the priority queue
    public int getCount() {
        return items.size();
    }

    public PriorityQueue() {
        items = new ArrayList<>();
    }

    public void enqueue(T item) {
        items.add(item);
        int childIndex = items.size() - 1;

        while (childIndex > 0) {
            int parentIndex = (childIndex - 1) / 2;

            if (items.get(childIndex).compareTo(items.get(parentIndex)) >= 0) {
                break;
            }

            swap(childIndex, parentIndex);
            childIndex = parentIndex;
        }
    }

    public T dequeue() {
        if (items.isEmpty()) {
            throw new NoSuchElementException("Priority queue is empty.");
        }

        T firstItem = items.get(0);
        int lastIndex = items.size() - 1;
        items.set(0, items.get(lastIndex));
        items.remove(lastIndex);

        int parentIndex = 0;

        while (true) {
            int leftChildIndex = 2 * parentIndex + 1;
            int rightChildIndex = 2 * parentIndex + 2;

            if (leftChildIndex >= items.size()) {
                break;
            }

            int minChildIndex = leftChildIndex;

            if (rightChildIndex < items.size() && items.get(rightChildIndex).compareTo(items.get(leftChildIndex)) < 0) {
                minChildIndex = rightChildIndex;
            }

            if (items.get(parentIndex).compareTo(items.get(minChildIndex)) <= 0) {
                break;
            }

            swap(parentIndex, minChildIndex);
            parentIndex = minChildIndex;
        }

        return firstItem;
    }

    public boolean contains(T item) {
        return items.contains(item);
    }

    private void swap(int index1, int index2) {
        T temp = items.get(index1);
        items.set(index1, items.get(index2));
        items.set(index2, temp);
    }
}
